package io.github.hadyang.leetcode.tencent;

import io.github.hadyang.leetcode.ListNode;
import org.junit.Test;

/**
 * 排序链表
 *
 * <p>在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 *
 * <p>示例 1:
 *
 * <p>输入: 4->2->1->3
 *
 * <p>输出: 1->2->3->4 示例 2:
 *
 * <p>输入: -1->5->3->4->0
 *
 * <p>输出: -1->0->3->4->5
 *
 * @author haoyang.shi
 */
public class Link932 {

  @Test
  public void test() {
    int[] ints = {4, 2, 1, 3};

    ListNode head = null;
    ListNode temp = null;
    for (int i : ints) {
      if (head == null) {
        head = new ListNode(i);
        temp = head;
      } else {
        temp.next = new ListNode(i);
        temp = temp.next;
      }
    }

    ListNode res = sortList(head);

    while (res != null) {
      System.out.println(res.val);
      res = res.next;
    }
  }

  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }

    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }

    ListNode mid = slow.next;
    slow.next = null;

    ListNode l1 = sortList(head);
    ListNode l2 = sortList(mid);

    return merge(l1, l2);
  }

  private ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) {
      return l2;
    }

    if (l2 == null) {
      return l1;
    }

    ListNode head, res;
    if (l1.val > l2.val) {
      head = l2;
      l2 = l2.next;
    } else {
      head = l1;
      l1 = l1.next;
    }
    res = head;

    while (l1 != null || l2 != null) {
      if (l1 == null) {
        head.next = l2;
        l2 = l2.next;
      } else if (l2 == null) {
        head.next = l1;
        l1 = l1.next;
      } else {
        if (l1.val > l2.val) {
          head.next = l2;
          l2 = l2.next;
        } else {
          head.next = l1;
          l1 = l1.next;
        }
      }
      head = head.next;
    }

    return res;
  }
}
